A conjecture of Borodin and a coloring of Grünbaum

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008     

On the asymmetric representatives formulation for the vertex coloring problem

We consider the vertex coloring problem, which can be stated as the problem of minimizing the number of labels that can be assigned to the vertices of a graph G such that each vertex receives at least one label and the endpoints of every edge are assigned different labels. In this work, the 0-1 integer programming formulation based on representative vertices is revisited to remove symmetry. The previous polyhedral study related to the original formulation is adapted and generalized. New versions of facets derived from substructures of G are presented, including cliques, odd holes and anti-holes and wheels. In addition, a new class of facets is derived from independent sets of G. Finally, a comparison with the independent sets formulation is provided.     

Distinguishing colorings of Cartesian products of complete graphs

We determine the values of s and t for which there is a coloring of the edges of the complete bipartite graph K_s,t which admits only the identity automorphism. In particular, this allows us to determine the distinguishing number of the Cartesian product of complete graphs.     

图的邻点可区别全色数的一个上界

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.
Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.     

Mycielski图的BBC染色

基于图G的Mycielski图M（G）,研究xb（G,TG）与xb（M（G）,T’）之间的关系以及xb（G,TG）与xb（M（G）,T＂）之间的关系,其中Tc为G的生成树,T’,T＂分别为M（G）的两类特殊生成树．并给出当G为二部图,完全图以及Halin图时,Xb（M（G）,T＂）的值．     

A new type of edge-derived vertex coloring

We study the minimum number of weights assigned to the edges of a graph G with no component K₂ so that any two adjacent vertices have distinct sets of weights on their incident edges. The best possible upper bound on this parameter is proved.     

Efficient algorithms for wavelength assignment on trees of rings

A fundamental problem in communication networks is wavelength assignment (WA): given a set of routing paths on a network, assign a wavelength to each path such that the paths with the same wavelength are edge-disjoint, using the minimum number of wavelengths. The WA problem is NP-hard for a tree of rings network which is well used in practice. In this paper, we give an efficient algorithm which solves the WA problem on a tree of rings with an arbitrary (node) degree using at most 3L wavelengths and achieves an approximation ratio of 2.75 asymptotically, where L is the maximum number of paths on any link in the network. The 3L upper bound is tight since there are instances of the WA problem that require 3L wavelengths even on a tree of rings with degree four. We also give a 3L and 2-approximation (resp. 2.5-approximation) algorithm for the WA problem on a tree of rings with degree at most six (resp. eight). Previous results include: 4L (resp. 3L) wavelengths for trees of rings with arbitrary degrees (resp. degree at most eight), and 2-approximation (resp. 2.5-approximation) algorithm for trees of rings with degree four (resp. six).     

Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

The Total Coloring Conjecture, in short, TCC, says that every simple graph is (Δ+2)-totally-colorable where Δ is the maximum degree of the graph. Even for planar graphs this conjecture has not been completely settled yet. However, every planar graph with Δ≥9 has been proved to be (Δ+1)-totally-colorable. In this paper, we prove that planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable.     

An inequality for the group chromatic number of a graph

We give an inequality for the group chromatic number of a graph as an extension of Brooks’ Theorem. Moreover, we obtain a structural theorem for graphs satisfying the equality and discuss applications of the theorem.     

一类广义积分integral from n=0 to ∞(((sin(θ_x))/x)~ndx)的计算

利用三角函数幂公式、L′Hospital法则、分部积分公式,得到含有三角函数的第一类广义积分integral from n=0 to ∞(((sin(θ_x))/x)~ndx)的计算公式,其中n≥1且θ≠0.